import { scan } from "./LexParser.js";

let syntax = {
    Program: [["Statement", "EOF"]],
    StatementList: [
        ["Statement"],
        ["StatementList", "Statement"]
    ],
    Statement: [
        ["ExpressionStatement"],
        ["IfStatement"],
        ["VariableDeclaration"],
        ["FunctionDeclaration"]
    ],
    IfStatement: [
        ["if", "(", "Expression", ")", "Statement"]
    ],
    VariableDeclaration: [
        ["var", "Identifier", ";"],
        ["let", "Identifier", ";"]
    ],
    FunctionDeclaration: [
        ["function", "Identifier", "(", ")", "{", "ExpressionStatement", "}"]
    ],
    ExpressionStatement: [
        ["Expression", ";"]
    ],
    Expression: [
        ["AdditiveExpression"]
    ],
    AdditiveExpression: [
        ["MultiplicativeExpression"],
        ["AdditiveExpression", "+", "MultiplicativeExpression"],
        ["AdditiveExpression", "-", "MultiplicativeExpression"]
    ],
    MutiplicativeExpression: [
        ["PrimaryExpression"],
        ["MultiplicativeExpression", "*", "PrimaryExpression"],
        ["MultiplicativeExpression", "/", "PrimaryExpression"]
    ],
    PrimaryExpression: [
        ["(", "Expression", ")"],
        ["Literal"],
        ["Identifier"]
    ],
    Literal: [
        ["Number"]
    ]

}

let hash = {}


function closure(state) {
    hash[JSON.stringify(state)] = state
    // 广度优先搜索
    let queue = []
    for (let symbol in state) {
        if (symbol.match(/^$/)) {
            continue
        }
        queue.push(symbol)
    }

    while (queue.length) {
        let symbol = queue.shift()
        console.log(symbol)
        if (syntax[symbol]) {
            for (let rule of syntax[symbol]) {
                if (!state[rule[0]]) {
                    queue.push(rule[0])
                }
                let current = state
                for (let part of rule) {
                    if (!current[part]) {
                        current[part] = {}
                    }
                    current = current[part]
                }
                current.$reduceType = symbol
                current.$reduceLength = rule.length
            }
        }
    }
    for (let symbol in state) {
        if (symbol.match(/^\$/)) {
            return
        }
        if (hash[JSON.stringify(state[symbol])]) {
            state[symbol] = hash[JSON.stringify(state[symbol])]
        } else {
            closure(state[symbol])
        }
    }
}

let end = {
    $isEnd: true
}

let start = {
    "Program": end
}



closure(start)


let source = `
    let a;
    a + 1;
`

export function parse(source) {
    let stack = [start]
    function reduce() {
        let state = stack[stack.length - 1]
        /*reduce to non-terminal symbols*/
        if (state.$reduceType) {
            let children = []
            for (let i = 0; i < state.$reduceLength; i++) {
                children.push(stack.pop())
            }
            // create a non-terminal symol and shift it

            let newsymbol = {
                type: state.$reduceType,
                children: children.reverse()
            }
            shift(newsymbol)
        } else {
            throw new Error("unexpected token")
        }
    }
    function shift(symbol) {
        let state = stack[stack.length - 1]
        if (symbol.type in state) {
            stack.push(state[symbol.type])
        } else {
            reduce()
            shift(symbol)
        }
    }

    for (let symbol/*terminal symbols*/ of scan(source)) {
        shift(symbol)
        //console.log(symbol)
    }
    reduce()
}


parse(source)
